1786 찾기 KMP

2018-03-31

1786 찾기 KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//
// 1786 찾기 KMP.cpp
// Algorithm
//
// Created by bbvch13531 on 2018. 3. 31..
// Copyright © 2018년 bbvch13531. All rights reserved.
//
#define MAX 1000000
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

void getPi(string);
void kmp(string,string);

vector<int> pi(MAX,0),res;

int main(void){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int ansSize;
char buf[MAX],ch;
string T,P;
// scanf("%[^\n]\n",buf);
// T=buf;
//
// scanf("%[^\n]",buf);
// P=buf;
// scanf는 비공백 문자부터 읽어들인다. 이 부분에서 에러났었음
getline(cin,T);
getline(cin,P);

// cout<<T<<endl<<P<<endl;
//getc gets 는 c++11이후 버전에서 deprecate되었다.
kmp(T,P);

ansSize=res.size();
cout<<ansSize<<endl;
for(int i=0;i<ansSize;i++) printf("%d ",res[i]+1);
return 0;
}
void getPi(string s){
int n=(int)s.size(),j=0;
fill(pi.begin(),pi.end(),0);
for(int i=1;i<n;i++){
//substring
while(j>0 && s[i]!=s[j]){
j = pi[j-1];
}
if(s[i]==s[j]){
j++;
pi[i]=j;
}
}
}
void kmp(string T,string P){
getPi(P);
int n=(int)T.size(),m=(int)P.size(),j=0;
for(int i=0;i<n;i++){
while (j>0 && T[i]!=P[j]) {
j=pi[j-1];
}
if(T[i]==P[j]){
if(j==m-1){
res.push_back(i-j);
j=pi[j];
}
else j++;
}
}
}